import java.util.*;

/**
 * 给定一个单词列表words和一个整数 k ，返回前k个出现次数最多的单词。
 *
 * 返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。
 * 输入: words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2
 * 输出: ["i", "love"]
 * 解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。
 * 注意，按字母顺序 "i" 在 "love" 之前。
 */
public class TopKFrequent {
    public static List<String> test(String[] words, int k){
      int size = words.length;
      Map<String,Integer> nums = new HashMap<>(size);
      for(int i = 0; i < size ; i++){
         String str = words[i];
         int num = 1;
         if (nums.containsKey(str)){
             num = nums.get(str) + num;
         }
         nums.put(str,num);
      }
      // 传入比较器
        // 因为是小顶堆，所以谁的字母大，谁在前面。谁value小谁在前面
        // 如果w1 和 w2 的数量相等，就需要找字母大的
        // 否则返回数量小的那个。
        // 排序（从小到大，取小的）
        // leetCode , coding ,love ,i
      PriorityQueue<String> pq = new PriorityQueue<>(
                (w1,w2) -> nums.get(w1).equals(nums.get(w2)) ? w2.compareTo(w1) : nums.get(w1)-nums.get(w2));
      for (String word : nums.keySet()){
          pq.add(word);
          if (pq.size() > k){
              pq.poll();
          }
      }
      List<String> res = new ArrayList<>();
      while (!pq.isEmpty()){
          res.add(pq.poll());
      }
      Collections.reverse(res);
      return res;
    }

    public static void main(String[] args) {
        String[] words =  {"i", "love", "leetcode", "i", "love", "coding"};
        List<String> res = topKFrequent(words,2);
        res.forEach(x->{
            System.out.println(x);
        });
    }

    public static List<String> topKFrequent(String[] words, int k) {
        int size = words.length;
        Map<String,Integer> map = new HashMap(size);
        for(String word : words){
            int num = 1;
            if(map.containsKey(word)){
                num = map.get(word) + num;
            }
            map.put(word,num);
        }
        // 创建小顶堆,自定义比较器
        // 比较器（因为是从小到大，所有会取小的那个）：如果a的数量等于b的数量，返回字母大的那个。否则，返回数量小的那个
        // 排序结果：LeetCode、code、love、i
        PriorityQueue<String> minHeap = new PriorityQueue<>(
                (a,b)-> map.get(a).equals(map.get(b)) ? b.compareTo(a) : map.get(a) - map.get(b)
      );
        for(String word : map.keySet()){
            minHeap.add(word);
            // 限制小顶堆的个数
            if(minHeap.size() > k){
                minHeap.poll();
            }
        }
        List<String> res = new ArrayList<>(k);
        while(!minHeap.isEmpty()){
            res.add(minHeap.poll());
        }
        Collections.reverse(res);
        return res;

    }
}
